/**
 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package std.core;

// NOTE: autogenerated file

export const KEY_NOT_FOUND = -1;

{% for T in ['boolean', 'byte', 'short', 'int', 'long', 'float', 'double', 'char', 'NullishType'] %}

{% if T != "NullishType" -%}
// C++ semantics
// (lower|upper)BoundSearch([1, 1, 2, 2, 2, 3, 3], 2, 0, 7)
//                                 ^        ^
//                                 |        |
//                                 |    upper bound
//                             lower bound

{% if T != "boolean" %}
/**
 * tries to find a lower bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex
 *
 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find lower bound of
 *
 * @param startIndex an index of arr to begin search with
 *
 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked
 *
 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex
 */
export function lowerBoundSearch(arr: {{T}}[], key: {{T}}, startIndex: int, endIndex: int): int {
    if (!checkRange(arr.length, startIndex, endIndex)){
        throw new RangeError("lowerBoundSearch: bounds verification failed")
    }

    let left: int = startIndex;
    let len: int = endIndex - startIndex;

    while (len > 0) {
        let half: int = len >>> 1;
        let middle: int = left + half;

        if (arr[middle] < key) {
            left = middle + 1;
            len -= half + 1;
        } else {
            len = half;
        }
    }

    return left;
}

/**
 *  tries to find a lower bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is arr.length
 *
 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find lower bound of
 *
 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length
 */
export function lowerBoundSearch(arr: {{T}}[], key: {{T}}): int {
    return lowerBoundSearch(arr, key, 0, arr.length);
}

/**
 * tries to find an upper bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex
 *
 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway
 *
 * @param startIndex an index of arr to begin search with
 *
 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked
 *
 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex
 */
export function upperBoundSearch(arr: {{T}}[], key: {{T}}, startIndex: int, endIndex: int): int {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new RangeError("upperBoundSearch: bounds verification failed")
    }

    let left: int = startIndex;
    let len: int = endIndex - startIndex;

    while (len > 0) {
        let half: int = len >>> 1;
        let middle: int = left + half;

        if (arr[middle] <= key) {
            left = middle + 1;
            len -= half + 1;
        } else {
            len = half;
        }
    }

    return left;
}

/**
 * tries to find an upper bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex
 *
 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway
 *
 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length
 */
export function upperBoundSearch(arr: {{T}}[], key: {{T}}): int {
    return upperBoundSearch(arr, key, 0, arr.length);
}
{% else %}
/**
 * tries to find a lower bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex
 *
 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find lower bound of. It may be not in arr, lower bound will present anyway
 *
 * @param startIndex an index of arr to begin search with
 *
 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked
 *
 * @returns index such (arr[index] < key) is false. If no such index is found than endIndex
 */
export function lowerBoundSearch(arr: boolean[], key: boolean, startIndex: int, endIndex: int): int {
    if (!checkRange(arr.length, startIndex, endIndex)){
        throw new RangeError("lowerBoundSearch: bounds verification failed")
    }

    let left: int = startIndex;
    let len: int = endIndex - startIndex;

    while (len > 0) {
        let half: int = len >>> 1;
        let middle: int = left + half;

        if (arr[middle] == false && key == true) {
            left = middle + 1;
            len -= half + 1;
        } else {
            len = half;
        }
    }

    return left;
}

/**
 * tries to find a lower bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Lower bound is an index of a first element, where (element < key) is false. If no such element is found than lower bound is endIndex
 *
 * @param arr array to find a lower bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find lower bound of. It may be not in arr, lower bound will present anyway
 *
 * @returns index such (arr[index] < key) is false. If no such index is found than arr.length
 */
export function lowerBoundSearch(arr: boolean[], key: boolean): int {
    return lowerBoundSearch(arr, key, 0, arr.length);
}

/**
 * tries to find an upper bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex
 *
 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway
 *
 * @param startIndex an index of arr to begin search with
 *
 * @param endIndex a last index to stop search in arr, i.e. arr[endIndex] is not checked
 *
 * @returns index such (key < arr[index]) is true. If no such index is found than endIndex
 */
export function upperBoundSearch(arr: boolean[], key: boolean, startIndex: int, endIndex: int): int {
    if (!checkRange(arr.length, startIndex, endIndex)) {
        throw new RangeError("upperBoundSearch: bounds verification failed")
    }

    let left: int = startIndex;
    let len: int = endIndex - startIndex;

    while (len > 0) {
        let half: int = len >>> 1;
        let middle: int = left + half;

        if (arr[middle] == false && key == true || arr[middle] == key) {
            left = middle + 1;
            len -= half + 1;
        } else {
            len = half;
        }
    }

    return left;
}

/**
 * tries to find an upper bound of a key in sorted arr.
 * The array has to be sorted before calling this function.
 * Upper bound is an index of a first element, where (key < element) is true. If no such element is found than upper bound is endIndex
 *
 * @param arr array to find a upper bound of a key. Has to be sorted, otherwise the answer is implementation-defined and may be incorrect
 *
 * @param key a value to find upper bound of. It may be not in arr, upper bound will present anyway
 *
 * @returns index such (key < arr[index]) is true. If no such index is found than arr.length
 */
export function upperBoundSearch(arr: boolean[], key: boolean): int {
    return upperBoundSearch(arr, key, 0, arr.length);
}
{%- endif %}
{%- endif %}

/**
 * Makes an array shallow copy
 *
 * @param src source array to be copied
 * @returns copy of `src`
 */
export function copyOf(src: {{T}}[]): {{T}}[] {
    const r = new {{T}}[src.length];
    try {
        copyTo(src, r, 0, 0, src.length);
    } catch (e) {
        // ignore
    }
    return r;
}

/**
 * copies src array into dst with respect to passed indexes.
 * dst must have enough space, otherwise out-of-bounds might occur
 *
 * @param src source array to be copied
 *
 * @param dst destination array
 *
 * @param dstStart index of dst to start from
 *
 * @param srcStart index of src to start from
 *
 * @param srcEnd last index of src to copy, exclusive, i.e. src[srcEnd] is not copied
 *
 * @example: copy src to dst
 * ```
 * copyTo(src, dst, 0, 0, src.length)
 * ```
 */
export function copyTo(src: {{T}}[], dst: {{T}}[], dstStart: int, srcStart: int, srcEnd: int): void {
    if (!checkRange(src.length, srcStart, srcEnd)) {
        throw new ArrayIndexOutOfBoundsError("copyTo: src bounds verification failed")
    }
    if (!checkRange(dst.length, dstStart, dst.length)) {
        throw new ArrayIndexOutOfBoundsError("copyTo: dst bounds verification failed")
    }
    if (!((srcEnd - srcStart) <= (dst.length - dstStart))) {
        throw new ArrayIndexOutOfBoundsError("Destination array must have enough space")
    }

    let j: int = dstStart;
    for (let i: int = srcStart; i < srcEnd; i++) {
        dst[j] = src[i];
        j++;
    }
}

{%- endfor %}
